Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра електронних
обчислювальних машин
Звіт
про виконання лабораторної роботи № 6
з курсу „ Теорія колективної поведінки інтелектуальних систем ”
Тема:
Ітераційна дилема ув’язненого
Виконав:
ст. гр. КІ-4
Львів – 2005
Мета: Ознайомитись з принципами співвідношення співпраці та суперництва в колективі агентів.
Загальні відомості
Для дослідження принципів співвідношення співпраці та суперництва використовується модель колективної поведінки під назвою "дилема ув’язненого" [1,3,4,5]. Дилема ув’язненого це гра двох осіб з не нульовою сумою (general-sum game). Кожний з гравців має дві можливості: співпрацювати (C - cooperate) чи протидіяти (D - defect). Якщо перший гравець протидіє, то якщо другий буде співпрацювати, то отримає за свою наївність найбільше у грі покарання (S), тоді як перший гравець отримає найбільше у грі заохочення (T) за свою підступність. В іншому випадку, якщо другий гравець буде також протидіяти, то обидва вони отримають однакове невелике покарання (P) за взаємну протидію. Якщо обидва гравця співпрацюють, то вони отримають невелике заохочення (R) за добре ставлення один до одного.
Дилема ув’язненого має зміст, якщо T>R>P>S, де R>(S+T)/2.
Матриця гри для дилеми ув’язненого виглядає наступним чином
Один з можливих варіантів гри: T = 5, R = 3, P = 1, S = 0.
Ітераційна дилема ув’язненого (iterated prisoner’s dilemma, IPD) – це гра з багатокроковим повторенням, в якій кожний з опонентів пам’ятає деяку кількість (глибина пам’яті) результатів минулих розіграшів. Згідно теорії ігор оптимальною (стійкою) стратегією в однокроковій IPD є протидія (D) (див. основне припущення теорії ігор та принцип обережності). В той же час при збільшені кількості кроків виникає задача максимізації середнього виграшу окремого гравця, яка не має тривіального рішення. Це означає, що постійна протидія не гарантує максимального середнього виграшу в IPD.
При дослідженні ітераційної дилеми ув’язненого розглядають наступні стратегії поведінки гравця (IPD-агента):
ALLC: завжди співпрацювати;
ALLD: завжди протидіяти;
TFT (Tit for tat, "зуб за зуб"): спочатку співпрацювати, потім віддзеркалювати дії опонента;
Grim ("невблаганний"): співпрацювати до першої протидії, потім завжди протидіяти;
Stochastic: обирати співпрацю та протидію випадково з фіксованими ймовірностями (стаціонарне випадкове середовище) та ін. [2].
В найпростішому випадку в стратегії (алгоритмі) поведінці гравця враховується результат лише попередньої партії (ітерації) гри. Зі збільшенням глибини пам’яті гравця стратегія (алгоритм) його поведінки суттєво ускладнюється.
Ітераційна дилема ув’язненого для двох агентів (N=2) узагальнюється для випадку, коли N>2, за допомогою механізму випадкової парної взаємодії (див. адаптивне управління з наслідуванням).
Текст програми
/* Copyright (c) 2005 alb. All Rights Reserved.
* Multiagent systems Lab * Computer Engineering Department
* Lviv Polytechnic National University
* ===============================================
* Multiagent Systems. Lab work 06.
* Multiagent design II: Iterated Prisoners Dilemma (iterated general-sum game)
*
* Here user (student) or RL-agent are in IPD with opponent called IPD-agent.
* Available strategies (set of actions) are {C,D} C=1 -> cooperate, D=2 -> defect.
* Payoff matrix for players (used in each iteration of game)
* | C#2 | D#2 |
* _______|_______|_______|
* C#1 | R1,R2 | S1,T2 |
* _______|_______|_______|
* D#1 | T1,S2 | P1,P2 |
* _______|_______|_______|
* requirements: T > R > P > S, and R > (S + T) / 2.
* example: T = 5, R = 3, P = 1, S = 0.
* The aim is to obtain maximum total win over T iterations.
* Implemented here IPD-agents are ALLC, ALLD, Stochastic, Grim, TFT.
*/
#include "stdafx.h"
int T = 5, R = 3, P = 1, S = 0;
int t; // current time step
int Time = 50; // maximum number of time ...
